/*
 * Topology.h is used to define data structures
 * and functions of the network. The userinter-
 * face is defined in class Topology:
 * Topology()---------------initialization
 * construct(string path)---build topo from file
 * floyd_warshall()---------calculate shortest path
*/


#ifndef TOPO_H
#define TOPO_H

#include <iostream>
#include <stdio.h>
#include <string>
#include <list>
#include <map>
#include <vector>

using namespace std;

#ifndef LINK_H
#define LINK_H
struct Link
{
	int dst;
	double weight;
};

class HNode
{
public:
	int num;
	list<Link> connects;
	HNode *previous;
	HNode *next;
	HNode()
	{
		num = 0;
		connects.clear();
		previous = next = NULL;
	}
	HNode(int n)
	{
		num = n;
		connects.clear();
		previous = next = NULL;
	}
	/*
	 * constructor for HNode
	*/
	HNode(int n, int size, int conn[], double weight[])
	{
		num = n;
		connects.clear();
		int i = 0;
		for (i = 0; i < size; i++)
		{
			Link nl;
			nl.dst = conn[i];
			nl.weight = weight[i];
			connects.push_back(nl);
		}
		previous = next = NULL;
	}
	/*
	 * connect the current node to dst,
	 * return true if not contained in connects
	 * false if already contained
	*/
	bool connect(int dst, double weight = 1)
	{
		list<Link>::iterator it;
		for (it = connects.begin(); it != connects.end(); it++)
		{
			if ((*it).dst == dst) return false;
		}
		Link nl;
		nl.dst = dst;
		nl.weight = weight;
		connects.push_back(nl);
		return true;
	}
	/*
	 * disconnect the current node to dst,
	 * return true if the link exists,
	 * false if not exists
	*/
	bool disconnect(int dst)
	{
		list<Link>::iterator it;
		for (it = connects.begin(); it != connects.end(); it++)
		{
			if ((*it).dst == dst)
			{
				connects.erase(it);
				return true;
			}
		}
		return false;
	}
};
#endif

class Topology
{
private:
	/*
	 * total number of nodes in the topology
	*/
	int num;
	/*
	 * keeps a list of nodes
	*/
	
	/*
	 * keeps a map from node number to HNode Struct
	*/
	map<int, HNode> fnode;	
	bool update;
	/*
	 * Constructor
	*/
public:
	list<HNode> nodes;
	vector<vector<double> > distance;
	map<string, double> dis_distance;
	map<string, double> links;
	map<string, string> path;
	typedef vector<string> single_path;
	map<string, single_path> dis_path;
	map<string, int> path_number;
	Topology()
	{
		num = 0;
		nodes.clear();
		fnode.clear();
		path.clear();
		distance.clear();
		dis_distance.clear();
		links.clear();
		dis_path.clear();
		path_number.clear();
		update = false;
	}
	bool insertHNode(HNode n)
	{
		list<HNode>::iterator it;
		for (it = nodes.begin(); it != nodes.end(); it++)
		{
			if ((*it).num == n.num) return false;
		}
		nodes.push_back(n);
		num++;
		fnode[num] = n;
		update = false;
		return true;
	}
	bool insertHNode(int node)
	{
		list<HNode>::iterator it;
		for (it = nodes.begin(); it != nodes.end(); it++)
		{
			if ((*it).num == node) return false;
		}
		HNode newHNode(0);
		newHNode.num = node;
		nodes.push_back(newHNode);
		num++;
		fnode[node] = newHNode;
		update = false;
		return true;
	}
	/*
	 * delete a node from the topology
	 *
	*/
	bool deleteHNode(int node)
	{
		list<HNode>::iterator it;
		for (it = nodes.begin(); it != nodes.end(); it++)
		{
			if ((*it).num == node) return false;
		}
		list<Link>::iterator dst;
		for (dst = (*it).connects.begin(); dst != (*it).connects.end(); dst++)
		{
			map<int, HNode>::iterator nit;
			if (!((nit = fnode.find((*dst).dst)) == fnode.end()))
			{
				(*nit).second.disconnect(node);
			}
		}
		(*it).connects.clear();
		map<int, HNode>::iterator fit;
		if (!((fit = fnode.find(node)) == fnode.end()))
		{
			fnode.erase(fit);
		}
		update = false;
		return true;
	}
	/*
	 * add link between src-dst
	 * src.connect(dst) && dst.connect(src)
	 * true if added succesfully
	 * false if src/dst not exists or add failed
	*/
	bool addLink(int src, int dst, double weight = 1)
	{
		list<HNode>::iterator sit, dit;
		bool sfnd = false, dfnd = false;
		for (sit = nodes.begin(); sit != nodes.end(); sit++)
		{
			if ((*sit).num == src)
			{
				sfnd = true;
				break;
			}
		}
		if (!sfnd) return false;
		for (dit = nodes.begin(); dit != nodes.end(); dit++)
		{
			if ((*dit).num == dst)
			{
				dfnd = true;
				break;
			}
		}
		if (!dfnd) return false;
		if ((*sit).connect(dst, weight) && (*dit).connect(src, weight))
		{
			links[x(src, dst)] = weight;
			links[x(dst, src)] = weight;
			update = false;
			return true;
		}
		else return false;
	}
	/*
	 * delete link between src-dst
	 * src.disconnect(dst) && dst.disconnect(src)
	 * true if deleted succesfully
	 * false if src/dst not exists or delete failed
	*/
	bool delLink(int src, int dst)
	{
		list<HNode>::iterator sit, dit;
		bool sfnd = false, dfnd = false;
		for (sit = nodes.begin(); sit != nodes.end(); sit++)
		{
			if ((*sit).num == src)
			{
				sfnd = true;
				break;
			}
		}
		if (!sfnd) return false;
		for (dit = nodes.begin(); dit != nodes.end(); dit++)
		{
			if ((*dit).num == dst)
			{
				dfnd = true;
				break;
			}
		}
		if (!dfnd) return false;
		if ((*sit).disconnect(dst) && (*dit).disconnect(src)) 
		{
			map<string, double>::iterator disit;
			if ((disit = links.find(x(src, dst))) != links.end())
			{
				links.erase(disit);
			}
			if ((disit = links.find(x(dst, src))) != links.end())
			{
				links.erase(disit);
			}
			update = false;
			return true;
		}
		else return false;
	}
	bool hasHNode(int node)
	{
		return (fnode.find(node) != fnode.end());
	}
	bool construct(string path)
	{
		FILE *input;
		if (!(input = fopen(path.c_str(), "r")))
		{
			cout << "cannot open file!\n";
			//exit(1);
		}
		int n;
		fscanf(input, "%d", &n);
		int i;
		int src, dst;
		double weight = 0.0;
		for (i = 0; i < n; i++)
		{
			fscanf(input, "%d%d%lf", &src, &dst, &weight);
			if (!this->hasHNode(src))
			{
				this->insertHNode(src);
			}
			if (!this->hasHNode(dst))
			{
				this->insertHNode(dst);
			}
			this->addLink(src, dst, weight);
		}
		update = false;
		fclose(input);
		return true;
	}
	/*
	 * string x() is used for map<string, *>'s key
	 * x(i, j)="i.j."
	*/
	string x(int i, int j)
	{
		string s = "";
		char xy[10000];
		sprintf(xy, "%d.%d.", i, j);
		s = xy;
		return s;
	}
	string x(HNode i, HNode j)
	{
		string s = "";
		char xy[10000];
		sprintf(xy, "%d.%d.", i.num, j.num);
		s = xy;
		return s;
	}
	/*
	 * floyd_warshall() calculates the shortest path between
	 * every src, dst pair in the topology, distance is used
	 * to store the total weight between src and dst, while 
	 * path is used to store the shortest path, in the form 
	 * of path["i.j."]="i.m1.m2.m3. ... .mn.j."
	 * it will return false if the path has been calculated
	*/
	bool floyd_warshall()
	{
		if (update) return false; //already calculated
		list<HNode>::iterator ii, ij;
		int i, j, k;
		distance.clear();
		//vector<vector<double> > dist;
		//dist.clear();
		distance.resize(nodes.size());
		for (i = 0; i < nodes.size(); i++)
		{
			distance[i].resize(nodes.size());
		}
		for (ii = nodes.begin(); ii != nodes.end(); ii++)
		{
			for (ij = nodes.begin(); ij != nodes.end(); ij++)
			{
				map<string, double>::iterator disit;
				std::string xy = x(*ii, *ij);
				if ((disit = links.find(xy)) == links.end())
				{
					distance[(*ii).num][(*ij).num] = -1;
					continue;
				}
				distance[(*ii).num][(*ij).num] = (*disit).second;
			}
		}

		for (k = 0; k < nodes.size(); k++)
		{
			for (i = 0; i < nodes.size(); i++)
			{
				double distik = distance[i][k];
				if (distik == -1) continue;
				for (j = 0; j < nodes.size(); j++)
				{
					if (i == j) continue;
					double distkj = distance[k][j];
					if (distkj == -1) continue;
					double distij = distance[i][j];
					if (distij == -1 || distik + distkj < distij)
					{
						distance[i][j] = distik + distkj;
					}
				}
			}
		}
		update = true;
		cout << "Simple Floyd Warshall Compeleted...\n";
		return true;
	}
	bool distribute_floyd_warshall()
	{
		if (update) return false; //already calculated
		list<HNode>::iterator i, j, k;
		dis_path.clear();
		dis_distance.clear();
		path_number.clear();
		for (i = nodes.begin(); i != nodes.end(); i++)
		{
			for (j = nodes.begin(); j != nodes.end(); j++)
			{
				map<string, double>::iterator disit;
				string xy = x(*i, *j);
				if ((disit = links.find(xy)) == links.end())
				{
					dis_distance[xy] = -1;
					continue;
				}
				single_path newpath = vector<string>();
				newpath.push_back(xy);
				dis_path.insert(std::pair<string, single_path>(xy, newpath));
				path_number.insert(std::pair<string, int>(xy, 1));
				dis_distance[xy] = (*disit).second;
			}
		}
		cout << "flyd init\n";
		for (k = nodes.begin(); k != nodes.end(); k++)
		{
			for (i = nodes.begin(); i != nodes.end(); i++)
			{
				string ik = x(*i, *k);
				double distik = dis_distance[ik];
				if (dis_distance[ik] == -1) continue;
				for (j = nodes.begin(); j!= nodes.end(); j++)
				{
					if ((*i).num == (*j).num) continue;
					string kj = x(*k, *j);
					string ij = x(*i, *j);
					double distkj = dis_distance[kj];
					if (distkj == -1) continue;
					double distij = dis_distance[ij];
					if (distij == -1 || distik + distkj < distij)
					{
						dis_distance[ij] = distik + distkj;
						int path_n = path_number[ik] * path_number[kj];
						path_number[ij] = path_n;
						single_path newpath = vector<string>();
						vector<string>::iterator it;
						for (it = dis_path[ik].begin(); it != dis_path[ik].end(); it++)
						{
							newpath.push_back((*it));
						}
						for (it = dis_path[kj].begin(); it != dis_path[kj].end(); it++)
						{
							newpath.push_back((*it));
						}
						map<string, single_path>::iterator diit;
						if ((diit = dis_path.find(ij)) != dis_path.end())
						{
							dis_path.erase(diit);
						}
						dis_path.insert(std::pair<string, single_path>(ij, newpath));
					}
					if (distij != -1 && distik + distkj == distij)
					{
						map<int, string>::iterator allpath;
						int ii, jj;
						path_number[ij]++;
						vector<string>::iterator it;
						for (it = dis_path[ik].begin(); it != dis_path[ik].end(); it++)
						{
							dis_path[ij].push_back((*it));
						}
						for (it = dis_path[kj].begin(); it != dis_path[kj].end(); it++)
						{
							dis_path[ij].push_back((*it));
						}
					}
				}
			}
		}
		update = true;
		return true;
	}
};

#endif